package cn.bellychang.wangzheng.skiplist;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ChangLiang
 * @date 2021/2/5
 */
public class SkipListMap<K extends Comparable<K>, V> {

    private static final double PROMOTION_FACTOR = 0.8d;

    private static final byte HEAD_TYPE = -1;

    private static final byte TAIL_TYPE = 1;

    private static final byte DATA_TYPE = 0;

    private Node head;

    private Node tail;

    private int size;

    private int height;

    private int maxHeight;

    private Random random;

    public SkipListMap(int maxHeight) {
        head = new Node(null, null, HEAD_TYPE);
        tail = new Node(null, null, TAIL_TYPE);
        head.right = tail;
        tail.left = head;
        size = 0;
        this.height = 1;
        this.maxHeight = maxHeight;
        random = new Random();
    }

    /**
     * 要考虑这个key在索引层的情况
     * @param key
     * @return
     */
    public V remove(K key) {
        Node equalNode = this.findLessOrEqualNode(key);
        if (equalNode.type == HEAD_TYPE) {
            throw new NoSuchElementException("no key: [" + key + "] entry");
        }

        V tempVal = equalNode.value;
        if (equalNode.key.compareTo(key) == 0) {
            while (equalNode != null) {
                equalNode.left.right = equalNode.right;
                equalNode.right.left = equalNode.left;
                equalNode = equalNode.up;
            }
            size--;
            return tempVal;
        } else {
            throw new NoSuchElementException("no key: [" + key + "] entry");
        }
    }

    public V get(K key) {
        Node node = this.findLessOrEqualNode(key);
        if (node.left == null || node.key.compareTo(key) != 0) {
            throw new NoSuchElementException("no key: [" + key + "] entry");
        } else {
            return node.getValue();
        }
    }

    public SkipListMap add(K key, V value) {
        // 第1层已经插入了
        Node lessOrEqualNode = findLessOrEqualNode(key);
        Node newNode = new Node(key, value, DATA_TYPE);

        // upperFloorNode <-> newNode <-> upperFloorNode.right
        newNode.right = lessOrEqualNode.right;
        newNode.left = lessOrEqualNode;
        lessOrEqualNode.right.left = newNode;
        lessOrEqualNode.right = newNode;

        // 这里是维护第2层开始的索引层
        int currentLevel = 2;

        while (random.nextDouble() < PROMOTION_FACTOR && currentLevel <= maxHeight) {
            if (currentLevel > height) {
                addEmptyLevel();
            }

            // 向链表左侧scan 通过这个while找到左侧哪个有向上的upper Node

            // 情况1：如果上一层是新增的 只有dummyHead和dummyTail节点
            // lessOrEqualNode还在这一层 这一层的dummyHead.up是一定存在的

            // 情况2：如果是最高层 lessOrEqualNode = dummyHead

            // lessNode == null never could happen, because of head !=null and it will have an empty upper layer
            while (lessOrEqualNode.up == null) {
                lessOrEqualNode = lessOrEqualNode.left;
            }

            // lessOrEqualNode走到了上一层
            lessOrEqualNode = lessOrEqualNode.up;

            Node upperNewNode = new Node(key, value, DATA_TYPE);

            // Three-ways(up-down left-right right-left) connection should be established
            upperNewNode.down = newNode;
            newNode.up = upperNewNode;

            upperNewNode.right = lessOrEqualNode.right;
            upperNewNode.left = lessOrEqualNode;
            lessOrEqualNode.right.left = upperNewNode;
            lessOrEqualNode.right = upperNewNode;

            // perhaps after this newNode promotion to upper layer,
            // this upperNewNode still need to promote to the next upper layer
            newNode = upperNewNode;

            currentLevel++;
        }

        size++;
        return this;
    }

    private void addEmptyLevel() {
        Node upperHead = new Node(null, null, HEAD_TYPE);
        Node upperTail = new Node(null, null, TAIL_TYPE);

        upperHead.right = upperTail;
        upperHead.down = this.head;
        this.head.up = upperHead;

        upperTail.left = upperHead;
        upperTail.down = this.tail;
        this.tail.up = upperTail;

        // head and tail move upwards
        this.head = upperHead;
        this.tail = upperTail;

        height++;
    }

    /**
     *
     * @param key
     * @return
     */
    private Node findLessOrEqualNode(K key) {
        Node temp = head;
        for (; ; ) {
            while (temp.right.type != TAIL_TYPE && temp.right.key.compareTo(key) <= 0) {
                temp = temp.right;
            }
            if (Objects.nonNull(temp.down)) {
                temp = temp.down;
            } else {
                break;
            }
        }
        return temp;
    }


    class Node {
        private K key;
        private V value;
        private byte type;
        private Node left, right, up, down;

        public V getValue() {
            return value;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Node(K key, V value, byte type) {
            this.key = key;
            this.value = value;
            this.type = type;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            return builder.append(Optional.ofNullable(key).orElse((K) "null").toString())
                    .append("|")
                    .append(Optional.ofNullable(value).orElse((V) "null").toString())
                    .toString();
        }
    }

    @Override
    public String toString() {
        List<String> list = new ArrayList<>(height);
        StringBuilder builder = new StringBuilder();
        Node headTemp = head;
        for (int i = 1; i <= height; i++) {
            Node temp = headTemp;
            while (temp != null) {
                builder.append(temp.toString())
                        .append("->");
                temp = temp.right;
            }
            list.add(builder.toString().substring(0, (builder.length() - 2)));
            builder.delete(0, builder.length());
            if (headTemp.down != null) {
                headTemp = headTemp.down;
            } else {
                break;
            }
        }
        return list.stream().collect(Collectors.joining("\\next line\\"));
    }
}
